package main

import "fmt"

func main() {

	//fmt.Println(canJump([]int{50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,1,4}))
	//fmt.Println(canJump([]int{8,2,4,4,4,9,5,2,5,8,8,0,8,6,9,1,1,6,3,5,1,2,6,6,0,4,8,6,0,3,2,8,7,6,5,1,7,0,3,4,8,3,5,9,0,4,0,1,0,5,9,2,0,7,0,2,1,0,8,2,5,1,2,3,9,7,4,7,0,0,1,8,5,6,7,5,1,9,9,3,5,0,7,5}))
	//fmt.Println(canJump([]int{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43}))
	fmt.Println(canJump([]int{3, 2, 1, 0, 4}))
	///fmt.Println(canJump([]int{1,2,2,6,3,6,1,8,9,4,7,6,5,6,8,2,6,1,3,6,6,6,3,2,4,9,4,5,9,8,2,2,1,6,1,6,2,2,6,1,8,6,8,3,2,8,5,8,0,1,4,8,7,9,0,3,9,4,8,0,2,2,5,5,8,6,3,1,0,2,4,9,8,4,4,2,3,2,2,5,5,9,3,2,8,5,8,9,1,6,2,5,9,9,3,9,7,6,0,7,8,7,8,8,3,5,0}))
}

func canJump(nums []int) bool {
	if len(nums) == 1 {
		return true
	}
	queue := []int{0}
	max := 3
	for len(queue) > 0 {
		for i := 1; i <= nums[queue[0]]; i++ {
			if queue[0]+nums[queue[0]] >= len(nums)-1 {
				return true
			}
			if queue[0]+i+nums[queue[0]+i] > max {
				max = queue[0] + nums[queue[0]]
				queue = append(queue, queue[0]+i)
			}
		}
		queue = queue[len(queue)-1:]
		if nums[queue[0]] == 0 {
			return false
		}
	}
	return false
}

func canJump1(nums []int) bool {
	if len(nums) == 1 {
		return true
	}
	queue := []int{0}
	max := 0
	for len(queue) > 0 {
		for i := 1; i <= nums[queue[0]]; i++ {
			if index := queue[0] + i; index+nums[index] > max {
				max = index + nums[index]
			}
		}
		if max >= len(nums)-1 {
			return true
		}
		if max < len(nums)-1 && nums[max] == 0 {
			return false
		}
	}
	return false

}
